package newcoder_exp.meituan;
import java.text.DecimalFormat;
import java.util.*;


import org.junit.Test;

import utils.BracketUtils;
public class Meituan4 {
    
    //1. 最多有多少点存在同一条直线上【149】
    class SolutionX { //错解：存在精度问题
        public int maxPointsX(int[][] points) {
            
            //使用k,t的形式存储一条直线 y = k * x + t
            int len = points.length, x1, y1, x2, y2;
            Set<String> lines = new HashSet<>();
            DecimalFormat df = new DecimalFormat("#.000");
            for (int i = 0; i < len; i++) {
                x1 = points[i][0];
                y1 = points[i][1];
                for (int j = i + 1; j < len; j++) {
                    x2 = points[j][0];
                    y2 = points[j][1];
                    int d = x2 - x1;
                    if (d == 0) continue; //当前的两点是同一点
                    double k = Double.parseDouble(df.format(((double)(y2 - y1)) / ((double)d)));
                    double t = y1 - k * x1;
                    lines.add(k + "," + t); //set有去重的行为
                }
            }
            Map<double[], Integer> map = new HashMap<>();
            for (String s: lines) {
                String[] str = s.split(",");
                double k = Double.parseDouble(str[0]);
                double t = Double.parseDouble(str[1]);
                map.put(new double[]{k, t}, 0);
            }

            int res = 0;
            for (int i = 0; i < len; i++) {
                for (double[] wt:map.keySet()) {
                    double k = wt[0], t = wt[1];
                    if (Math.abs(k * points[i][0] + t - points[i][1]) < 0.001) {
                        int cur = map.get(wt) + 1;
                        map.put(wt, cur);
                        res = Math.max(res, cur);
                    }
                }
            }

            for (double[] wt: map.keySet()) {
                if (map.get(wt) == res) System.out.println(Arrays.toString(wt));
            }
            return res;
        }
    }

    class Solution {

        //不存储这个方程的形式，而是直接采取三重循环
        public int maxPoints(int[][] points) {
            int len;
            int res = 0;
            for (int i = 0; i < (len = points.length); i++) {
                for (int j = i + 1; j < len; j++) {
                    int cur = 0;
                    //确实可能存在同一条直线两次甚至两次以上【即被两组不同的x,y确定的同一条直线，
                    //如11 22 33 44 => 11 22, 11 33...都会让剩下的两个遍历一遍】，
                    //但是那样只会导致多遍历几趟，并不会影响res最终的值
                    for (int k = 0; k < len; k++) {
                        if (k != i && k != j) {
                            if (test2(points[i][0], points[j][0], points[i][1], 
                            points[j][1], points[k][0], points[k][1])) cur++;
                            res = Math.max(res, cur);
                        }
                    }
                }
            }
            //res遍历的是在这个直线上的点的数量，最终需要加上确定直线的两个点
            return res + 2;
        }


        public boolean test(int x1, int x2, int y1, int y2, int x, int y) {
            return ((long)(y2 - y1)) * (x - x1) == ((long)(y - y1)) * (x2 - x1);
        }

        //原理： (y2 - y1) / (x2 - x1) == (y2 - y) / (x2 - x) 可以保证三点一线， 但是本身存在精度不准
        //将左右两个分式通过最大公约数划到最简，只需保证 分子 == 分子， 分母 == 分母 即可
        public boolean test2(int x1, int x2, int y1, int y2, int x, int y) {
            if (x1 == x2 || x2 == x) return x1 == x; //有两个点位于同一个垂直线，看第三个是否位于这条垂直线
            if (y1 == y2 || y2 == y) return y1 == y; //两点位于同一个水平线......
            int ans1 = gcd(y2 - y1, x2 - x1);
            int ans2 = gcd(y2 - y, x2 - x);
            int a = (y2 - y1) / ans1, b = (x2 - x1) / ans1;
            int c = (y2 - y) / ans2, d = (x2 - x) / ans2;
            return a == c && b == d;
        }

        //无需保证a>b, 因为若是a<b, 在一轮循环后, a = b, b = a % b = a
        //这也隐式的解决了判断三个点是否同一个斜率，只需要判断任意两个点的y,x差的公约数相等，而不用管y差大还是x差大
        public int gcd(int a, int b) {
            while (b != 0) {
                int c = a % b;
                if (c == 0) return b;
                a = b;
                b = c;
            }
            return b;
        }
    }

    @Test
    public void test() {
        // int[][] nums = BracketUtils.to2DArray("[[1,1],[2,2],[3,3]]");
        // int[][] nums = BracketUtils.to2DArray("[[1,1],[2,2],[3,3]]");
        int[][] nums = BracketUtils.to2DArray("[[1, 1], [23, 57], [69, 50], [73, 81], [22, 20], [81, 66], [93, 92], [3, 4], [20, 40], [19, 38], [7, 3], [54, 92], [80, 73], [10, 31], [15, 69], [8, 72], [94, 66], [46, 61], [18, 79], [53, 25], [45, 94], [85, 63], [25, 32], [36, 59], [51, 43], [5, 29], [73, 64], [77, 71], [66, 40], [77, 45], [92, 19], [44, 84], [25, 69], [21, 72], [78, 54], [12, 23], [48, 68], [45, 52], [17, 82], [69, 25], [3, 91], [5, 62], [17, 6], [87, 29], [27, 22], [72, 6], [91, 59], [80, 84], [10, 48], [8, 31], [46, 54], [1, 19], [47, 26], [34, 34], [77, 87], [0, 29], [67, 41], [76, 31], [98, 74], [43, 72], [13, 86], [85, 14], [81, 74], [31, 18], [82, 69], [10, 53], [5, 96], [30, 45], [82, 56], [81, 20], [97, 47], [29, 53], [8, 39], [88, 63], [76, 35], [53, 86], [17, 92], [82, 39], [13, 27], [42, 96], [65, 26], [29, 22], [7, 48], [11, 37], [64, 63], [0, 58], [93, 21], [39, 31], [42, 55], [7, 7], [91, 39], [47, 60], [91, 92], [53, 95], [91, 72], [28, 8], [79, 46], [32, 23], [28, 17], [1, 10]]");

        Solution s = new Solution();
        int res = s.maxPoints(nums);
        // int res = s.gcd(15, 6);
        System.out.println(res);
    }


    @Test
    public void test1() {
        int[][] nums = new int[100][2];
        Set<String> set = new HashSet<>();
        Random r = new Random();
        for (int i = 0;i < 100; i++) {
            nums[i] = new int[2];
            int a = 1, b = 1;
            while (set.contains(a + "_" + b)) {
                a = r.nextInt(100);
                b = r.nextInt(100);
            }
            set.add(a + "_" + b);
            nums[i][0] = a;
            nums[i][1] = b;
        }
        System.out.println(Arrays.deepToString(nums));
    }


    /* 
        310 最小高度树：想办法求得一个树结构（没有环的无向图就是树）的根节点，使得这棵树的高度最高
        等于求：求一个图结构的“中心节点”，即 位于两个最远边缘节点的路径中心

        方案：
        反向BFS：
        使用一个Map，记录所有结点的度
        先加入所有度为1的点（即边缘节点）入队
        一个个出队，并将与之相连的顶点的度减一【为了增加遍历速度，需要设定每个节点的出入度Map】
        再对度为1的节点执行同样的操作
        直到队列中节点数量为1，结束并返回
    */
    class Solution2 {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n <= 2) return new ArrayList<>(){{add(edges[0][0]); add(edges[0][1]);}};
            Map<Integer, Set<Integer>> out = new HashMap<>(); //邻接表
            int[] dict = new int[n];

            int count = n;
            for (int i = 0; i < edges.length; i++) {
                int n1 = edges[i][0], n2 = edges[i][1];
                dict[n1]++;
                dict[n2]++;

                if (out.containsKey(n1)) out.get(n1).add(n2);
                else out.put(n1, new HashSet<>(){{add(n2);}});
                if (out.containsKey(n2)) out.get(n2).add(n1);
                else out.put(n2, new HashSet<>(){{add(n1);}});
            }

            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                if (dict[i] == 1) {
                    queue.offer(i);
                    count--;
                }
            }
            while (count > 0) { //还有度大于1的节点
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int cur = queue.poll();
                    Set<Integer> adj = out.get(cur);
                    for (int next: adj) {
                        dict[next]--;
                        out.get(next).remove(cur);
                        if (dict[next] == 1) {
                            count--;
                            queue.offer(next);
                        }
                    }
                }
            }
            return new ArrayList<>(queue);
        }
    }

    @Test
    public void test2() {
        int[][] nums = BracketUtils.to2DArray("[[3,0],[3,1],[3,2],[3,4],[5,4]]");
        Solution2 s = new Solution2();
        System.out.println(s.findMinHeightTrees(6, nums));
    }
}
